/**
 * 很难过，回溯超时了
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function (beginWord, endWord, wordList) {
    if (!wordList.includes(endWord)) return 0;
    let minLength = Infinity;
    dfs(beginWord, endWord, wordList, [beginWord])

    function dfs(beginWord, endWord, wordList, valArr) {
        if (beginWord === endWord) {
            minLength = Math.min(minLength, valArr.length)
            return
        }

        for (let i = 0; i < wordList.length; i++) {
            if (isLadderWord(beginWord, wordList[i])) {
                if (valArr.includes(wordList[i])) {
                    continue
                } else {
                    valArr.push(wordList[i])
                }
                dfs(wordList[i], endWord, wordList, valArr)
                valArr.pop()
            }
        }
    }

    return minLength === Infinity ? 0 : minLength;
};

function isLadderWord(w1, w2) {
    let w1Len = w1.length, w2Len = w2.length, count = 0;
    if (w1Len !== w2Len) return false
    for (let i = 0; i < w1Len; i++) {
        if (w1[i] === w2[i]) count++
    }
    if (count === w1Len - 1) return true
    return false
}



/**
 * 广搜可以，看到最短路径，优先想到广搜
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function (beginWord, endWord, wordList) {
    if (!wordList.includes(endWord)) return 0;
    let hasUsedSet = new Set(),
        minLength = 0;

    let queue = [beginWord];
    hasUsedSet.add(beginWord);
    while (queue.length > 0) {
        let len = queue.length;
        minLength++
        for (let q = 0; q < len; q++) {
            let word = queue.shift()
            if (word === endWord) {
                return minLength
            }
            for (let i = 0; i < wordList.length; i++) {
                if (isLadderWord(word, wordList[i])) {
                    // 如果已经遍历过，则不再遍历，否则可能陷入死循环。如果不再遍历的话，是正确的，因为如果遍历过，再次遍历，只能增加最长的路径
                    if (hasUsedSet.has(wordList[i])) {
                        continue
                    } else {
                        queue.push(wordList[i])
                        hasUsedSet.add(wordList[i])
                    }
                }
            }
        }
    }

    return 0;
};

function isLadderWord(w1, w2) {
    let w1Len = w1.length, w2Len = w2.length, count = 0;
    if (w1Len !== w2Len) return false
    for (let i = 0; i < w1Len; i++) {
        if (w1[i] === w2[i]) count++
    }
    if (count === w1Len - 1) return true
    return false
}